//
//  puzzle.c
//  
//
//  Created by Jialin Liu on 3/23/13.
//
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>
#include <sys/time.h>
#include <limits.h>
int num_puzzle;
int m=0;
//node data strucutre
typedef struct node
{
    //node * parent=NULL;
    int * position;  //tile positions;
    int cost;         //store the cost;
    unsigned int hash;
    unsigned int hash_parent;
}node;

node *livearray;
//=(node *)malloc(sizeof(node)*100000);
//cost functions
int cost(int * position){
    int cost=0;
    for (int i=0;i<num_puzzle; i++) {
        if (i!=position[i]) {
            cost++;
        }
    }
    return cost;

}

int manhattan(int * position){
    int cost=0;
    int num_p=(int)sqrt(num_puzzle);
    for(int i=0;i<num_puzzle;i++) {
        if(i!=position[i]){
            cost+=abs(i/num_p-position[i]/num_p)+abs(i%num_p-position[i]%num_p);
        }
    }
    return cost;
}

//hash function
    struct hash_entry {
	   node * pairing;
           unsigned int key_length; /**< length of key */
           //struct hash_entry *next; /**< next entry */
	   unsigned int hash;
	   unsigned int hash_parent;
   };
   
   struct hash_table {
           unsigned int nchains;
           struct hash_entry **chain;
   };
   
   /**
    * Hash a string, returning a 32bit value.  The hash algorithm used is
    * Fowler Noll Vo - a very fast and simple hash, ideal for short strings.
    * See http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash for more details.
    *
    * \param  datum   The string to hash.
    * \param  len     Pointer to unsigned integer to record datum's length in.
    * \return The calculated hash value for the datum.
    */
   
unsigned int hash_string_fnv(char *datum,unsigned int * length)
{
           int i;
           unsigned int z = 0x811c9dc5;
	   char *start=datum;
           if (datum == NULL)
                   return 0;

                        //return true;
         for(i=0;i<num_puzzle;i++){
                   z *= 0x01000193;
                   z ^= *datum++;
           }
           *length=datum-start;
//	   printf("%d\n",*length);
           return z;
	
}

   
   /**
    * Create a new hash table, and return a context for it.  The memory consumption
    * of a hash table is approximately 8 + (nchains * 12) bytes if it is empty.
    *
    * \param  chains Number of chains/buckets this hash table will have.  This
    *                should be a prime number, and ideally a prime number just
    *                over a power of two, for best performance and distribution.
    * \return struct hash_table containing the context of this hash table or NULL
    *         if there is insufficent memory to create it and its chains.
    */
   
   struct hash_table *hash_create(unsigned int chains)
   {
           struct hash_table *r = (struct hash_table*)malloc(sizeof(struct hash_table));
   
           if (r == NULL) {
                   printf("Not enough memory for hash table.");
                   return NULL;
           }
   
           r->nchains = chains;
           r->chain = (struct hash_entry **)malloc(chains*sizeof(struct hash_entry *));
   
           if (r->chain == NULL) {
                   printf("Not enough memory for %d hash table chains.", chains);
                   free(r);
                   return NULL;
           }
   
           return r;
   }
   
   /**
    * Destroys a hash table, freeing all memory associated with it.
f ((key_length == e->key_length) &&
                                   (memcmp(key, e->pairing, key_length) == 0))
    *
    * \param  ht    Hash table to destroy.  After the function returns, this
    *               will nolonger be valid.
    */
   /*
   void hash_destroy(struct hash_table *ht)
  {
           unsigned int i;
   
           if (ht == NULL)
                   return;
   
           for (i = 0; i < ht->nchains; i++) {
                   if (ht->chain[i] != NULL) {
                           struct hash_entry *e = ht->chain[i];
                           while (e) {
                                   struct hash_entry *n = e->next;
                                   free(e->pairing);
                                   free(e);
                                   e = n;
                           }
                   }
           }
   
           free(ht->chain);
           free(ht);
   }
  */
   /**
    * Adds a key/value pair to a hash table.  If the key you're adding is already
    * in the hash table, it does not replace it, but it does take precedent over
    * it.  The old key/value pair will be inaccessable but still in memory until
    * hash_destroy() is called on the hash table.
    *
    * \param  ht     The hash table context to add the key/value pair to.
    * \param  key    The key to associate the value with.  A copy is made.
    * \param  value  The value to associate the key with.  A copy is made.
    * \return true if the add succeeded, false otherwise.  (Failure most likely
    *         indicates insufficent memory to make copies of the key and value.
    */
   
   bool hash_add(struct hash_table *ht, char *key, node *value)
   {
           unsigned int h, c, v;
           struct hash_entry *e=(struct hash_entry *)malloc(sizeof(struct hash_entry));
   
           if (ht == NULL || key == NULL || value == NULL)
                   return false;
   
          if (e == NULL) {
                   printf("Not enough memory for hash entry.\n");
                   return false;
           }
   
           h = hash_string_fnv(key, &(e->key_length));
	   value->hash=h;
	   //printf("%d\n",h);
           c = h % ht->nchains;
//	   printf("Before:%d's parent is:%d\n",h,value->hash_parent);
           e->pairing=(node *)malloc(sizeof(node));
           e->hash=h;
	   e->hash_parent=value->hash_parent;
          if(e->pairing==NULL)
	   {
		printf("not enough memory for node");
		return false;
	   }
           //memmove(e->pairing,key,e->key_length+1);
	   memcpy(e->pairing,value,sizeof(node));
    //       e->next = ht->chain[c];
           ht->chain[c] = e;
//	   printf("%d \n",c);
/*	   (livearray+m)->hash=value->hash;
	   (livearray+m)->hash_parent=value->hash_parent;
          // (livearray+m)->position=(int *)malloc(sizeof(int)*num_puzzle);
	    (livearray+m)->position=value->position;
*/
           return true;
   }
  
   /**
    * Looks up a the value associated with with a key from a specific hash table.
    *
    * \param  ht     The hash table context to look up the key in.
    * \param  key    The key to search for.
    * \return The value associated with the key, or NULL if it was not found.
    */
   
   //node *hash_get(struct hash_table *ht, const char *key)
    bool hash_get(struct hash_table *ht, char *key)
   {
           unsigned int h, c, key_length;
           struct hash_entry * e=(struct hash_entry *)malloc(sizeof(struct hash_entry));
   
           if (ht == NULL || key == NULL)
                   return false;
   
           h = hash_string_fnv(key, &key_length);
           c = h % ht->nchains;
//           memcpy(e ,ht->chain[c],sizeof(struct hash_entry));
            if(ht->chain[c]){
		e=ht->chain[c];
	   if(e->hash==h)     
 	   return true;}
  	   else   	
           return false;
   }
   int * hash_get_position(struct hash_table *ht, unsigned int *hash_parent)
   {
           unsigned int h, c, key_length;
           struct hash_entry * e=(struct hash_entry *)malloc(sizeof(struct hash_entry));

           if (ht == NULL )
                   return false;

          // h = hash_string_fnv(key, &key_length);
           c = *hash_parent % ht->nchains;
//           memcpy(e ,ht->chain[c],sizeof(struct hash_entry));
            
                e=ht->chain[c];
	  node * temp=(node *)malloc(sizeof(node));
	temp->position=(int *)malloc(sizeof(int)*16);
	 memcpy(temp,e->pairing,sizeof(node));
	*hash_parent=e->hash_parent;
           
           return temp->position;
   }

/*
 int * hash_get_position(unsigned int *hash_parent){
	for(int i=0;i<m;i++)
	{
		if((livearray+i)->hash==*hash_parent){
		int *position=(int *)malloc(sizeof(int)*num_puzzle);
		position=(livearray+i)->position;
		*hash_parent=(livearray+i)->hash_parent;
		return position;
		}
	}
}

   */

/*heap tree to store the priority*/
void heap_insert(node * livelist,int * heapsize, node * element){
	*heapsize+=1;
        livelist[*heapsize] = *element; /*Insert in the last place*/
        /*Adjust its position*/
        int now = * heapsize;
        while(livelist[now/2].cost > element->cost) 
        {
                livelist[now] = livelist[now/2];
                now /= 2;
        }
        livelist[now] = *element;
}

node * heap_pop(node *livelist,int * heapSize){
	
        node * minElement=(node *)malloc(sizeof(node));
	node * lastElement=(node *)malloc(sizeof(node));
	int child,now;
        *minElement = livelist[1];
        *lastElement = livelist[*heapSize];//last element
        if(*heapSize>1){
        /* now refers to the index at which we are now */
        for(now = 1; now*2 <= *heapSize ;now = child)
        {
                /* child is the index of the element which is minimum among both the children */ 
                /* Indexes of children are i*2 and i*2 + 1*/
                child = now*2;
                /*child!=heapSize beacuse heap[heapSize+1] does not exist, which means it has only one 
                  child */
                if(child != *heapSize && livelist[child+1].cost < livelist[child].cost ) 
                {
                        child++;
                }
                /* To check if the last element its ot not it suffices to check if the last element
                   is less than the minimum element among both the children*/
                if(lastElement->cost > livelist[child].cost)
                {
                        livelist[now] = livelist[child];
                }
                else /* It fits there */
                {
                        break;
                }
        }	
        livelist[now] = *lastElement;
        *heapSize-=1;
 	}
	else 
	{
	*heapSize-=1;
        }
        return minElement;
}

char * array_string(int * array)
{
        char *text=(char *)malloc(sizeof(char)*num_puzzle);
        for(int i=0;i<num_puzzle;i++)
        text[i]='a'+array[i];
        return text;
}

/*check the puzzle is solvable*/
bool solvable(int puzzle []){
  int i,j;
  int less=0;
  int mark;
  for(i=0;i<num_puzzle;i++){
   if(puzzle[i]==0)
   mark=i;
   for(j=i+1;j<num_puzzle;j++)
   {
	if (puzzle[j]<puzzle[i])
	less++;
   }
  }
  int num_p=(int)sqrt(num_puzzle);
  if(((mark/num_p)+(mark%num_p))%2!=0)
    less++;
   
  if (less%2==0)//is even
     return true;
  else
     return false;
}

bool isgoal(int * positions)
{
 int i;
 int error=0;
 for(i=0;i<num_puzzle;i++)
 {
  if(positions[i]!=i)
  error++;
 }
 if(error==0)
   return true;
 else
 return false;
}
 node * move(node * mynode, int * nummove){
  unsigned int hash_parent,parent_length;
  hash_parent=hash_string_fnv(array_string(mynode->position),&parent_length);
 int num_p=(int)sqrt(num_puzzle);
  //node testnode;
  size_t size=sizeof(int)*num_puzzle;
  int *pos=(int *)malloc(size);
  memcpy(pos,mynode->position,size);

  node * livenode=(node *)malloc(sizeof(node)*4);//maximum 4 nodes
  livenode->position=(int *)malloc(size);
  int i;
  for(i=0;i<4;i++){
  (livenode+i)->hash_parent=hash_parent;
  (livenode+i)->position=(int *)malloc(size);
  }
  //find where is zero
  int zeropos;
  for(i=0;i<num_puzzle;i++)
  { 
	
	if(pos[i]==0){
	zeropos=i;
	break;}
  } 
  *nummove=0;//number of move 
  int temp;
 // int num_p=(int)sqrt(num_puzzle);
  node * leftnode=(node *)malloc(sizeof(node));
  leftnode->position=(int *)malloc(size);
  memcpy(leftnode->position,pos,size);
  node * rightnode=(node *)malloc(sizeof(node));
  rightnode->position=(int *)malloc(size);
  memcpy(rightnode->position,pos,size);
  node * upnode=(node *)malloc(sizeof(node));
  upnode->position=(int *)malloc(size);
  memcpy(upnode->position,pos,size);
  node * downnode=(node *)malloc(sizeof(node));
  downnode->position=(int *)malloc(size);
  memcpy(downnode->position,pos,size);

   //can move left;
   if((num_puzzle==16&&zeropos%4!=0)||(num_puzzle==25&&zeropos%5!=0)||(num_puzzle==9&&zeropos%3!=0)){
   temp=leftnode->position[zeropos-1];
  leftnode->position[zeropos-1]=0;
  leftnode->position[zeropos]=temp;
  memcpy(livenode[*nummove].position,leftnode->position,size);
  *nummove+=1;
  }
  //can move right?
  if(num_puzzle==16&&(zeropos+1)%4!=0||(num_puzzle==25&&(zeropos+1)%5!=0)||(num_puzzle==9&&(zeropos+1)%3!=0)){
  temp=rightnode->position[zeropos+1];
  rightnode->position[zeropos+1]=0;
  rightnode->position[zeropos]=temp;
  memcpy(livenode[*nummove].position,rightnode->position,size);
  *nummove+=1;
  }
  
  //can we move up
  if((num_puzzle==16&&zeropos>3)||(num_puzzle==25&&zeropos>4)||(num_puzzle==9&&zeropos>2)){
  
  temp=upnode->position[zeropos-num_p];
  upnode->position[zeropos-num_p]=0;
  upnode->position[zeropos]=temp;
  memcpy(livenode[*nummove].position,upnode->position,size);
   *nummove+=1;
  }
  //can we move down
 if((num_puzzle==16&&zeropos<12)||(num_puzzle==25&&zeropos<20)||(num_puzzle==9&&zeropos<6)){
  temp=downnode->position[zeropos+num_p];
  downnode->position[zeropos+num_p]=0;
  downnode->position[zeropos]=temp;
  memcpy(livenode[*nummove].position,downnode->position,size);
  *nummove+=1;
  }
  
  return livenode;
 }
int timeval_subtract(struct timeval *result, struct timeval *t2, struct timeval *t1)
{
    long int diff = (t2->tv_usec + 1000000 * t2->tv_sec) - (t1->tv_usec + 1000000 * t1->tv_sec);
    result->tv_sec = diff / 1000000;
    result->tv_usec = diff % 1000000;

    return (diff<0);
}
int main()
{
 struct timeval tvBegin, tvEnd, tvDiff;

printf("read input\n");
scanf("%d",&num_puzzle);
int * input_node=(int *)malloc(sizeof(int)*num_puzzle);
for(int num_i=0;num_i<num_puzzle;num_i++)
scanf("%d",input_node+num_i);
// int input_node[16]={1,5,2,3,4,9,6,7,8,0,10,11,12,13,14,15};
//int input_node[16]={1,5,2,3,4,9,6,7,8,10,0,15,12,13,11,14};
//int input_node[16]={1,2,6,0,4,9,5,3,8,10,11,7,12,13,14,15}; 
//int input_node[16]={4,1,0,2,8,5,7,3,9,13,6,11,12,14,10,15};
//int input_node[16]={1,5,0,3,4,6,2,7,8,9,10,11,12,13,14,15};
//int input_node[16]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0};
 struct hash_table * mytable;
 mytable=hash_create(1000000);
//livearray=(node *)malloc(sizeof(node)*1000000);

 if(mytable==NULL)
 {
   printf("table malloc error\n");
   return -1;
 }
//livearray=(node *)malloc(sizeof(node)*100000); 
 //check if it is goal state
clock_t t1, t2;
 gettimeofday(&tvBegin, NULL);
 t1 = clock(); 
int numsteps=0;
 if(solvable(input_node)){
        
  	if(isgoal(input_node))
 	 {
		printf("goal is here\n");
		return 0;
  	 }
    node * firstnode=(node *)malloc(sizeof(node));
    unsigned int firstlength;
    firstnode->hash=hash_string_fnv(array_string(input_node),&firstlength);
    firstnode->cost=manhattan(input_node);
    firstnode->position=input_node;
    firstnode->hash_parent=firstnode->hash;
    unsigned int root_hash=firstnode->hash;
    //store in the hash table

    if(!hash_add(mytable,array_string(input_node),firstnode))
    return false;
	m++;
    //enqueue the priority queue;
     node * livelist=(node *)malloc(sizeof(node)*1000000);
     int heapsize=0;
     livelist[0].cost=-INT_MAX;
     heap_insert(livelist, &heapsize,firstnode);

     while(heapsize>0){//if queue is not empty
     numsteps++;
     node * k=heap_pop(livelist,&heapsize);
     //generate its children
     int imove,nummove;
     int bound_cost=k->cost;
     node * livenode=move(k,&nummove);//expand children;
     
     for(imove=0;imove<nummove;imove++)
     {
 	//hash_get(struct hash_table *ht, const char *key)
       if(!hash_get(mytable,array_string((livenode+imove)->position)))
        {
		//not duplicate->input into hash table
		hash_add(mytable,array_string((livenode+imove)->position),&livenode[imove]);
		m++;
 	        //check if is the goal state;
 		if(isgoal((livenode+imove)->position))
		{
		t2 = clock();   
gettimeofday(&tvEnd, NULL);
timeval_subtract(&tvDiff, &tvEnd, &tvBegin);
    printf("%ld.%06ld\n", tvDiff.tv_sec, tvDiff.tv_usec);
		 float diff = (((float)t2 - (float)t1) / 1000000.0F ) * 1000;   
		// printf("%f",diff);   
		printf("goal is found\n");
		printf("time cost:%f\n",diff);
		printf("number of nodes:%d\n",m);
		printf("heapsize:%d\n",heapsize);
		int gi;
		for(gi=0;gi<num_puzzle;gi++){
 		printf("%2d ",(livenode+imove)->position[gi]);
		if(num_puzzle==16){
                if(gi==3||gi==7||gi==11||gi==15)
                printf("\n");}
		if(num_puzzle==9){
		if(gi==2||gi==5||gi==8)
		printf("\n");}
		if(num_puzzle==25){
		if(gi==4||gi==9||gi==14||gi==19||gi==24)
		printf("\n");
		}
		}
		//printf("hashsize:%d\n",);
	//	printf("heapsize:%d\n",heapsize);
	//	printf("numsteps:%d\n",numsteps);
	
		int solutionmove=0;
		unsigned int hash_parent=livenode[imove].hash_parent;
		int *output_position;
		
		while(hash_parent!=root_hash){
		solutionmove++;
		output_position=hash_get_position(mytable,&hash_parent);
	        for(gi=0;gi<num_puzzle;gi++){
		printf("%2d ",output_position[gi]);
		if(num_puzzle==16){
		if(gi==3||gi==7||gi==11||gi==15)
		printf("\n");}
                if(num_puzzle==9){
                if(gi==2||gi==5||gi==8)
                printf("\n");}
                if(num_puzzle==25){
                if(gi==4||gi==9||gi==14||gi==19||gi==24)
                printf("\n");
                }
		}
	        	
		printf("\n");
		}
		for(gi=0;gi<num_puzzle;gi++){
                printf("%2d ",input_node[gi]);
                if(num_puzzle==16){
                if(gi==3||gi==7||gi==11||gi==15)
                printf("\n");}
                if(num_puzzle==9){
                if(gi==2||gi==5||gi==8)
                printf("\n");}
                if(num_puzzle==25){
                if(gi==4||gi==9||gi==14||gi==19||gi==24)
                printf("\n");
                }
                }

		printf("solutionmove:%d\n",solutionmove);
		return 0;		
		}
		//put into the queue
		else
		{
		//calculate cost
		int newcost=manhattan((livenode+imove)->position)+1+cost((livenode+imove)->position);
		(livenode+imove)->cost=newcost;
		//if(newcost<bound_cost)
		 heap_insert(livelist,&heapsize,livenode+imove);	
		}
        }
     }
    }

 }
 else 
printf("not solvable\n");
//hash_destroy(mytable);
}
